class Solution {
public:
    int majorityElement(vector<int>& nums) {
       return majorityElement_rec(nums, 0, nums.size()-1);
    }

    int majorityElement_rec(vector<int>& nums, int l, int r){
        if(l == r)
            return nums[l];
        
        int mid = (l + r) / 2;
        int left = majorityElement_rec(nums, l, mid);
        int right = majorityElement_rec(nums, mid + 1, r);

        int left_count = count_rec(nums, left, l, r);
        int right_count = count_rec(nums, right, l, r);

        if(left_count < right_count)
            return right;
        else
            return left;
    }

    int count_rec(vector<int>& nums, int target, int l, int r){
        int count = 0;
        for(int i=l; i<=r; i++){
            if(nums[i] == target)
                count++;
        }
        return count;
    }
};